Reducing memory requirements are important, especially for those systems supporting decoding of the high definition television (HDTV) standard. For example, an MPEG-2 video decoder integrated system capable of decoding high definition sequences, as well as standard definition sequences, normally requires access to an external video memory (DRAM) of at least 80 Mbits through a common interface. Typically, in such an application, the video memory may be configured according to the following frame buffers. A bit buffer for compressed data is set according to the MPEG-2 standard at 9,500,000 bits. An I-frame buffer for the I-picture (Intra-picture) is decompressed in a 4:2:0 format and a P-frame buffer for the decompressed P-picture (Predicted-picture) is in a 4:2:0 format. In addition, a B-frame buffer for the decompressed B-picture (Bidirectionally Predicted Picture) is in a 4:2:0 format. Each frame buffer in the 4:2:0 format may occupy an amount of memory given by: ##EQU1##
Therefore, the actual total amount of memory requirement for high definition television decoding will be: EQU 9,500,000+24,883,200+24,883,200+24,883,200=84,149,600 bits
By using fast synchronous memories such as SDRAM, decompression of the B-pictures can be optimized upon reception without storing them. This optimization reduces the external memory requirement to: EQU 9,500,000+24,883,200+24,883,200=59,266,400 bits
In view that the B-buffer is implemented on chip, reduction of the external memory requirements is necessary to convert the scanning of each 8.times.8 block. This conversion is defined in the MPEG-2 compressed bitstream for each row of the picture (field or frame), as required by the video display processing. Such a conversion macrocell is commonly referred to as a MACROBLOCK To RASTER SCAN CONVERTER .
Incorporated herein by reference in its entirety is European Patent Application No. 97830041.6, dated Feb. 6, 1997, which is assigned to the assignee of the present invention. This reference discloses an efficient tree-search vector quantization (TSVQ) technique for compressing digital video data to be stored in the external memory. This reduces the video memory requirement of the system. In practice, the memory required by the decoding system can be reduced by recompressing the pictures used as a reference for the prediction (I-, P- and B-pictures) after MPEG decompression, and before storing them in the external video memory. The same TSVQ compression technique is also useful in SQTV processors.
As previously described with respect to the above-referenced patent application, the effectiveness of a compression method based on the TSVQ technique is strongly influenced by the way the quantizer is chosen. The quantizer is used for quantizing the differences among the adjacent pel vectors. The present invention improves the effectiveness of the method described in referenced patent application by providing a more efficient way of selecting the quantizer, apart from other improving features.
As an illustrative example to highlight an object of the present invention, reference is made to the description of the MPEG-2 decoding system disclosed in the referenced patent application. The MPEG-2 decoding system utilizes a tree-search vector quantization technique for compressing digital video data to be stored in an external video memory. In particular, I is a digital picture represented by a matrix of M rows and N columns of pixels. I(y,x) is the pixel corresponding to row y and column x, and is coded with an integer number B of bits (binary digits). The I picture is separated into rectangular blocks having an R.times.C size (R rows and C columns). The maximum efficiency for the compression is obtained if R and C are chosen among the integer divisors of M and N, respectively.
The algorithm performs a compression of each block by exploiting only the data extracted from the block itself. The compression of each block is a reduction of the number of bits necessary for representing the block itself. This simplifies both access to the block in the stream of compressed data, and also the decompression of the block itself. The TSVQ compression mechanism exploits the correlation existing among adjacent pixels of a picture for reducing the number of bits necessary for a binary description of the picture itself. Considering a vector formed by J rows and K columns, the ideal effectiveness of the compression is obtained if J and K are chosen among the integer dividers of R and C, respectively. It is possible to approximate the value of a pixel vector by appropriately combining only the values of the pixels adjacent to it and forming a second pixel vector. This forms what is commonly referred to as a vector prediction.
It is therefore possible to reduce the amount of binary digits necessary for a digital representation of a picture by defining the prediction mechanism and by appropriately coding only a prediction error vector. This coding of the prediction error vector does not code each pixel. The more precise the vector prediction (and its components), the lower the entropy of the prediction error. That is, the number of bits necessary for coding the prediction error is lower.
In defining a scanning arrangement of the R.times.C block, for each J.times.K vector there exists another vector preceding it that may be used as the predictor of the vector itself. An exception is for the first one, which is not subject to any modification with respect to the values of its components. Let
V (i . . . i+J-1, j . . . j+K-1), PA1 OV (1 . . . J, 1 . . . K), first scan vector PA1 OV' (i . . . i+J-1, 1 . . . j+K-1), PA1 1) coding of the unmodified first vector V (1 . . . J, 1 . . . K) of an R.times.C block by vectors of T.times.K dimensions; PA1 2) selection and use of a scanning path of the R.times.C block by vectors of J.times.K dimension; PA1 3) selection of a partition in regions of the scan; PA1 4) selection and calculation of a measure of complexity for each region; PA1 5) quantization of the measure through binary search and coding of the quantizer; PA1 6) generation of a predictor vector of the current one to be quantized; PA1 7) division of the prediction error by the quantized complexity measure; PA1 8) quantization of the result of the division through binary search and coding of the quantizer; and PA1 9) repetition of steps 4 to 8 using the path defined in step 2 for all the vectors of the block R.times.C, and for all the regions in which the block has been partitioned.
i=1, . . . , [R-J+1] and PA2 j=1, . . . , [C-K+1] PA2 i=1, and PA2 j=1, 1+K, 2+K, C-K+1
be the vector comprising the pixels contained in the rectangular area determined by the following coordinates: top left coordinates (i, j), top right coordinates (i, j+K-1), bottom left coordinates (i+J-1, j), and bottom right coordinates (i+J-1, j+K-1). With respect to the arrangement of FIG. 9, the rectangular area is defined as follows:
The prediction error, E=V-V', is defined according to a scanning arrangement that is divided in regions so that each vector E belongs to only one region. The union of the regions forms the R.times.C block. A local complexity measure for each region is defined as the average value of the sum of the components of each vector E( ) in terms of its absolute value. Accordingly, j ranges between 1 and (C-K+1)/D, where D is a positive integer ranging between 1 and (C-K+1). Other measures could be used for determining the local complexity measure, such as the maximum value of the components.
A positive value is quantized with one of the G values stored in a table. The positive value represents the centroids of the areas in which the most general scalar statistic of the values have been divided. Such a partition minimizes the mean square error as compared to other possible partitions of the same statistic. Quantization table G is generated by using the Generalized Lloyd's Algorithm, which is well know to one skilled in the art.
Each component of the error prediction vector is divided by a quantized value G*. In this manner, the entropy of the prediction error statistic is further reduced towards a mean value equal to 0. This step of the algorithm increases the efficiency of the next quantization step, while reducing the quantization error of the error vector E. The quantization error of the error vector E is scaled by the gain G*, and is now referred to as E*.
For example, if D=2, the region R.times.C is subdivided into two zones. In the first zone, the value G1 is calculated. Value G1 is substituted (i.e., quantized) with G1* and is used to scale the E vectors. The E vectors are calculated in the first zone. The same procedure is used for the second zone, which leads to a different value of G2. Once the calculated region E* is defined, the error vector is quantized. That is, the error vector is replaced with one of the H vectors stored in a table. The error vector represents the centroids of the areas in which the most general vector statistic of a picture has been partitioned. This partition minimizes the mean square error as compared to other possible partitions of the same statistic.
The quantization table H is generated through the Generalized Lloyd's Algorithm. An advantage of using a TSVQ compression technique derives from the fact that the quantization process terminates after a number of comparisons are equal to the logarithm in base 2 of H. The TSVQ compression method may be applied to each block in which the picture is divided, through the following operations:
Steps 1) through 9) as previously listed for the TSVQ compression method are described and illustrated in greater detail in the following numbered sections. Each numbered section below corresponds with one of the steps listed in 1) through 9).
1) CODING OF THE UNMODIFIED FIRST VECTOR V (1 . . . J, 1 . . . K) OF AN R.times.C BLOCK. The R.times.C block is composed as follows:
A(1,1) A(1,2) A(1,3) A(1,4) A(1,5) A(1,6) A(1,7) A(1, C/K) A(2,1) A(2,2) A(2,3) A(2,4) A(2,5) A(2,6) A(2,7) A(2, C/K) A(3,1) A(3,2) A(3,3) A(3,4) A(3,5) A(3,6) A(3,7) A(3, C/K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A(R/J,1) A(R/J,2) A(R/J,4) A(R/J,4) A(R/J,5) A(R/J,6) A(R/J,7) A(R/J, C/K)
where A is a vector composed of J.times.K pixels. The first vector A(1, 1) is coded without any modification, according to its original resolution by B bits.
2) SELECTION AND USE OF A SCANNING PATH OF THE R.times.C BLOCK BY J.times.K DIMENSION VECTORS. The scan selected for generating the prediction error and the relative vector quantization may be as follows:
 - first row, A(1,1), A(1,2) A(1,C/K) - second row, A(2,1), A(2,2) A(2,C/K) - third row, A(3,1), A(3,2) A(3,C/K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - last row, A(R/J,1), A(R/J,2) A(R/J, C/K)
3) SELECTION OF A PARTITION IN REGIONS OF THE SCANNING. The scanning previously selected is further partitioned in regions that comprises a part of the prediction errors of the R.times.C region. Typically, symmetric partitions are preferred. The number of such partitions comprises between 1 and (C-K+1). For example, if D=2, then two partitions are obtained:
 FIRST REGION SECOND REGION A(1,1) A(1,2) A(1,3) A(1,4) A(1,C/2 * K) // A(1, (C/2 * K) + 1) A(1, C/K) A(2,1) A(2,2) A(2,3) A(2,4) A(2,C/2 * K) // A(2, (C/2 * K) + 1) A(2, C/K) A(3,1) A(3,2) A(3,3) A(3,4) A(3,C/2 * K) // A(3, (C/2 * K) + 1) A(3, C/K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A(R/J,1) A(R/J,2) A(R/J,3) A(R/J,C/2 * K) // A(R/J, (C/2 * K) + 1A(R/J, C/K)
Other partitions are possible.
4) SELECTION AND CALCULATION OF A MEASURE OF COMPLEXITY FOR EACH REGION. The complexity measure may be defined as the average value of the sum of the absolute values of the components of each predictor error vector. These errors belong to the same region in which the measure of complexity is calculated. Alternative measures are possible. An example of an alternative measurement is to use the average value of the maximum value of the components of each prediction error vector.
5) QUANTIZATION OF THE MEASURE THROUGH A BINARY SEARCH AND CODING OF THE QUANTIZER. Considering the use of a quantization table formed by an integer number G of scalar values, such a table belongs to a set making H possible to select G in a different manner for region to region. Each of these numbers G represents the centroid of a well defined partition of the statistic for the measures of complexity, as calculated by the Generalized Lloyd's Algorithm. Assuming that they are disposed at the nodes of a binary tree, and that G=7, then:
 G4 "00" G2 G5 "01" G1 G6 "10" G3 G7 "11"
The complexity measure calculated in step 4 is quantized in terms of G4, G5, G6 and G7. For example, assume that G is the value of the measurement. The differences (G-G2) and (G-G3) are then calculated, and it is assumed that the first difference is less than the second difference. The next step is to calculate (G-G4) and (G-G5). It is assumed that the second difference is less than the first difference. Therefore, G*=G5 is the value that better approximates G among those values available in the table. For the coding of G*, only two bits are necessary, such as 01 used in the example. The difference (G-Gi) may be calculated according to the L1 or L2 norms, or in a different way.
6) GENERATING A PREDICTION VECTOR FOR THE CURRENT ONE TO BE QUANTIZED. The prediction is of the spatial type, wherein the components of the prediction error vector are generated as sums and/or differences. These components may be weighted by appropriate coefficients corresponding to the pixels belonging to adjacent vectors. An example is illustrated below. For the prediction, use is made of the vector in the position that precedes the predicted one. For example, predictor A(1, 1) is used to predict A(1, 2), wherein A(1, 1) and A(1, 2) are two vectors with J=4 and K=1.
 A(1, 1) = P0 A(1, 2) = Q0 P1 Q1 P2 Q2 P3 Q3
The prediction vector is equal to
 E( ) = Q0 - P0 Q1 - P1 Q2 - P2 Q3 - P3
For each pixel Q of the block, the predictor to be adopted will be the pixel P in accordance with what was previously defined. It should be noted that such a predictor, following the previously illustrated scan order, has already been quantized and reconstructed. Therefore, it is not taken from the original picture. This allows for a better control of image quality, according to known ADPCM techniques.
7) DIVIDING THE PREDICTION ERROR BY THE QUANTIZED MEASURE OF COMPLEXITY. The predictor error E( ) belongs to the region wherein the measure G was calculated. Therefore, each component of E( ) is divided by the quantized measure G*, thus obtaining E*( ).
8) QUANTIZING THROUGH BINARY RESEARCH AND CODING OF THE QUANTIZER. It is assumed that the quantization table used is made up of H vectors, where each vector includes 4 integer components. Each of these vectors represents the centroid of a well defined partition of the prediction vector statistic, and are calculated through the Generalized Lloyd's Algorithm. Also, they are disposed at the nodes of a binary tree, with H equal to 15, illustrated as follows:
 H8 "000" H4 H9 "001" H2 H10 "010" H5 H11 "011" H1 H12 "100" H6 H13 "101" H3 H14 "110" H7 H15 "111" Notation: H2 and H3 are sons of H1 H4 and H5 are sons of H2 H7 and H6 are sons of H3 H8 and H9 are sons of H4 H10 and H11 are sons of H5 H12 and H13 are sons of H6 H14 and H15 are sons of H7
A son vector is defined as a vector whose components correspond to the arithmetic mean of the homologous components of a corresponding parent vector. The scaled error predictor E*( ) is quantized through H8, H9, H10, H11, H12, H13, H14 and H15. For example, the difference [E*( )-H2] and [E*( )-H3] is calculated, and the distance (e.g., Norm I2) equals the sum of the squares of the differences among the components of the two vectors. The distance is also calculated between the vector E*( ) and H2, and between the vector E*( ) and H3.
Assuming the second difference is less than the first difference, the next step is to calculate the distance between E*( ) and H6, and between E*( ) and H7. Assuming the first difference is less than the second difference, then the distance between E*( ) and H12, and between E*( ) and H13 will be calculated. If the latter difference is less than the first difference, then H13 will be the quantized vector of E*( ). This is the best value of approximation among those available in the above mentioned table. For the coding of H13, only three bits 101 are necessary for the considered example. ##STR1##
Only the vectors H8, H9, H10, H11, H12, H13, H14 or H15 can be the quantized vectors of E*( ), while the other vectors are used for determining which of those vectors are more similar to E*( ). Finally, as an alternative to the Norm I2, any other measurement of distance in the vectorial space may be utilized. For example, the Norm I1 is the sum of the modules of the differences among the homologous components of the two vectors. In this case, it is important to note that it is sufficient to have only one table for the chrominance and one table for the luminance because the error E*( ) has been scaled with G*.
FIG. 1 shows an MPEG2 video decoder which includes a TSVQ encoder and a TSVQ decoder for compression/decompression using a tree-search vector quantization for data stored in the video memory (DRAM). FIG. 2 shows the means for enabling or disabling the TSVQ recompression of data, depending on the functioning conditions as disclosed in the above referenced European patent application.